#include "main/utils.h"
using namespace std;

// *************************solution1**************************
int bfs1(const set<int>& set, std::set<int>& visited, int num) {
  queue<int> queue;
  queue.push(num);
  visited.insert(num);
  int length = 1;
  while (!queue.empty()) {
    int cur = queue.front();
    queue.pop();
    vector<int> neighbors = {cur - 1, cur + 1};
    for (auto neighbor : neighbors) {
      if (set.find(neighbor) != set.end() &&
          visited.find(neighbor) == visited.end()) {
        queue.push(neighbor);
        visited.insert(neighbor);
        ++length;
      }
    }
  }
  return length;
}

int longestConsecutive1(const vector<int>& vec) {
  set<int> set(vec.begin(), vec.end());
  int longest_length = 0;
  std::set<int> visited;
  for (int i = 0; i < vec.size(); ++i) {
    if (visited.find(vec[i]) == visited.end()) {
      int length = bfs1(set, visited, vec[i]);
      if (length > longest_length) {
        longest_length = length;
      }
    }
  }
  return longest_length;
}

// *************************solution2**************************
int bfs2(std::set<int>& set) {
  int num = *set.begin();
  set.erase(num);
  queue<int> queue;
  queue.push(num);
  int length = 1;
  while (!queue.empty()) {
    int cur = queue.front();
    queue.pop();
    vector<int> neighbors = {cur - 1, cur + 1};
    for (auto neighbor : neighbors) {
      if (set.find(neighbor) != set.end()) {
        queue.push(neighbor);
        set.erase(neighbor);
        ++length;
      }
    }
  }
  return length;
}

int longestConsecutive2(const vector<int>& vec) {
  set<int> set(vec.begin(), vec.end());
  int longest_length = 0;
  while (!set.empty()) {
    int length = bfs2(set);
    if (length > longest_length) {
      longest_length = length;
    }
  }
  return longest_length;
}

// *************************solution3**************************
int findFather(map<int, int>& fathers, int i) {
  if (fathers[i] != i) {
    fathers[i] = findFather(fathers, fathers[i]);
  }
  return fathers[i];
}

void merge(map<int, int>& fathers,
           map<int, int>& count,
           int i, int j) {
  int father_i = findFather(fathers, i);
  int father_j = findFather(fathers, j);
  if (father_i != father_j) {
    fathers[father_i] = father_j;
    int count_i = count[father_i];
    int count_j = count[father_j];
    count[father_j] = count_i + count_j;
  }
}

int longestConsecutive3(const vector<int>& vec) {
  set<int> set(vec.begin(), vec.end());
  map<int, int> fathers;
  map<int, int> count;
  for (int i = 0; i < vec.size(); ++i) {
    fathers[vec[i]] = vec[i];
    count[vec[i]] = 1;
  }
  for (auto num : vec) {
    vector<int> neighbors = {num + 1, num - 1};
    for (auto neighbor : neighbors) {
      if (set.find(neighbor) != set.end()) {
        merge(fathers, count, num, neighbor);
      }
    }
  }

  int max_length = 0;
  for (auto ele : count) {
    max_length = max(max_length, ele.second);
  }
  return max_length;
}

int main() {
  vector<int> vec = {10, 5, 9, 2, 4, 3};
  cout << longestConsecutive1(vec) << endl;
  cout << longestConsecutive2(vec) << endl;
  cout << longestConsecutive3(vec) << endl;

  return 0;
}
